package doing;

import com.study.common.ListNode;

import static com.study.util.SwapUtil.swap;

/**
 * 148. Sort List 排序链表
 * <p>
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 * <p>
 * 示例 1:
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * <p>
 * 示例 2:
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 * <p>
 * 2019-06-20 19:21
 **/
@SuppressWarnings("all")
public class SortList {

    public ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }

    void quickSort(ListNode head, ListNode tail) {
        if (head == tail || head.next == tail)
            return;

        int pivot = head.val;
        ListNode left = head;
        ListNode cur = head.next;

        while (cur != tail) {
            if (cur.val < pivot) {
                left = left.next;
                swap(left, cur);
            }
            cur = cur.next;
        }
        swap(head, left);
        quickSort(head, left);
        quickSort(left.next, tail);
    }
}